#include "common.h"
#include "sampler.h"

//things from NTL
#include <NTL/LLL.h>
#include <NTL/vector.h>
#include <NTL/ZZ.h>
#include <NTL/vec_ZZ.h>
#include <NTL/mat_ZZ.h>
#include <NTL/tools.h>
#include <NTL/RR.h>
#include <NTL/vec_double.h>

//things from standard library
#include <vector>
#include <stdlib.h>


/*
 * This class does a list sieve on the basis. 
 * It will support two ways to solve it, one always reducing some random 
 * lattice vector as much as possible and the other reducing it with 
 * probability inversely proportional to how short it will be, distributed 
 * according to a discrete Gaussian
 */
class ListSieve {
  public:
    ListSieve(mat_ZZ basis);
    //solves SVP using list_reduce
    vec solve();
    //solves SVP using g_list_reduce
    vec g_solve();

  private:
    double pi;
    long dimension;
    double t_; //t = log(dimension); used for sampleZ

    mat_ZZ B; //basis that will be given to us

    //returns random lattice vector by finding  sum of subset of basis vectors
    vec randomVec(mat_ZZ &basis);

    //returns random integer from discrete gaussian
    long sampleZ(double c, double s_squared);
    
    //adds t to the list keeping it sorted(assuming it already is)
    void sorted_add(vec *t, vector<vec> &list);

    //reduces t using vectors from list which we assume to be sorted
    void list_reduce(vec *t, vector<vec> &list);

    //adds t to the list keeping it sorted(assuming it already is) but not 
    //allowing duplicates
    void g_sorted_add(vec *t, vector<vec> &list);

    //returns v - c * a where c is samples from discrete Gaussian
    vec g_reduce(vec *v, vec *a);
    //reduces t using vectors from list, but with gaussian_reduce
    void g_list_reduce(vec *t, vector<vec> &list);
};
